#include"BinaryTree.h"
#include"Queue.h"

BTNode* BuyBinaryTreeNode(BTData x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc failed");
		exit(-1);
	}
	newnode->data = x;
	newnode->left = NULL;
	newnode->right = NULL;
	return newnode;
}

BTNode* BinaryTreeCreate(char* a, int n, int* i)
{
	if (a[*i] == '#')
	{
		*i = (*i) + 1;
		return NULL;
	}
	BTNode* root = BuyBinaryTreeNode(a[*i]);
	*i = (*i) + 1;
	root->left = BinaryTreeCreate(a, n, i);
	root->right = BinaryTreeCreate(a, n, i);
	return root;
}

int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}

int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->left == root->right)
	{
		return 1;
	}
	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

int BinaryTreeKLevelSize(BTNode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
		return 1;
	return BinaryTreeKLevelSize(root->left, k - 1) + BinaryTreeKLevelSize(root->right, k - 1);
}

int BinaryTreeLevelSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	if (root->left == root->right)
		return 1;
	int left = BinaryTreeLevelSize(root->left);
	int right = BinaryTreeLevelSize(root->right);
	return (left > right ? left : right) + 1;
}

void BinaryTreePrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	printf("%c  ", root->data);
	BinaryTreePrevOrder(root->left);
	BinaryTreePrevOrder(root->right);
}

void BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}

	BinaryTreePrevOrder(root->left);
	printf("%c  ", root->data);
	BinaryTreePrevOrder(root->right);
}

void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	BinaryTreePrevOrder(root->left);
	BinaryTreePrevOrder(root->right);
	printf("%c  ", root->data);
}

BTNode* BinaryTreeFind(BTNode* root, BTData x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->data == x)
		return root;
	BTNode* left = BinaryTreeFind(root->left, x);
	if (left)
	{
		return left;
	}
	else
	{
		return BinaryTreeFind(root->right, x);
	}
}

void BinaryTreeDestory(BTNode* root)
{
	if (root == NULL)
		return;
	BinaryTreeDestory(root->left);
	BinaryTreeDestory(root->right);
	free(root);
}

void BinaryTreeNonR(BTNode* root)
{
	Que q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* temp = QueueTop(&q);
		QueuePop(&q);
		printf("%c  ", temp->data);
		if (temp->left)
			QueuePush(&q, temp->left);
		if (temp->right)
			QueuePush(&q, temp->right);

	}
	printf("\n");
}